home *** CD-ROM | disk | FTP | other *** search
/ Software of the Month Club 2000 October / Software of the Month - Ultimate Collection Shareware 277.iso / pc / PROGRAMS / UTILITY / WINLINUX / DATA1.CAB / programs_-_include / ASM-MIPS / BITOPS.H < prev    next >
C/C++ Source or Header  |  1999-09-17  |  13KB  |  566 lines
  1. /*
  2.  * include/asm-mips/bitops.h
  3.  *
  4.  * This file is subject to the terms and conditions of the GNU General Public
  5.  * License.  See the file "COPYING" in the main directory of this archive
  6.  * for more details.
  7.  *
  8.  * Copyright (c) 1994 - 1997  Ralf Baechle (ralf@gnu.org)
  9.  */
  10. #ifndef __ASM_MIPS_BITOPS_H
  11. #define __ASM_MIPS_BITOPS_H
  12.  
  13. #include <linux/types.h>
  14. #include <linux/byteorder/swab.h>        /* sigh ... */
  15.  
  16. #ifdef __KERNEL__
  17.  
  18. #include <asm/sgidefs.h>
  19. #include <asm/system.h>
  20.  
  21. /*
  22.  * Only disable interrupt for kernel mode stuff to keep usermode stuff
  23.  * that dares to use kernel include files alive.
  24.  */
  25. #define __bi_flags unsigned long flags
  26. #define __bi_cli() __cli()
  27. #define __bi_save_flags(x) __save_flags(x)
  28. #define __bi_restore_flags(x) __restore_flags(x)
  29. #else
  30. #define __bi_flags
  31. #define __bi_cli()
  32. #define __bi_save_flags(x)
  33. #define __bi_restore_flags(x)
  34. #endif /* __KERNEL__ */
  35.  
  36. /*
  37.  * Note that the bit operations are defined on arrays of 32 bit sized
  38.  * elements.  With respect to a future 64 bit implementation it is
  39.  * wrong to use long *.  Use u32 * or int *.
  40.  */
  41. extern __inline__ void set_bit(int nr, void *addr);
  42. extern __inline__ void clear_bit(int nr, void *addr);
  43. extern __inline__ void change_bit(int nr, void *addr);
  44. extern __inline__ int test_and_set_bit(int nr, void *addr);
  45. extern __inline__ int test_and_clear_bit(int nr, void *addr);
  46. extern __inline__ int test_and_change_bit(int nr, void *addr);
  47.  
  48. extern __inline__ int test_bit(int nr, const void *addr);
  49. #ifndef __MIPSEB__
  50. extern __inline__ int find_first_zero_bit (void *addr, unsigned size);
  51. #endif
  52. extern __inline__ int find_next_zero_bit (void * addr, int size, int offset);
  53. extern __inline__ unsigned long ffz(unsigned long word);
  54.  
  55. #if (_MIPS_ISA == _MIPS_ISA_MIPS2) || (_MIPS_ISA == _MIPS_ISA_MIPS3) || \
  56.     (_MIPS_ISA == _MIPS_ISA_MIPS4) || (_MIPS_ISA == _MIPS_ISA_MIPS5)
  57.  
  58. /*
  59.  * These functions for MIPS ISA > 1 are interrupt and SMP proof and
  60.  * interrupt friendly
  61.  */
  62. #include <asm/mipsregs.h>
  63.  
  64. /*
  65.  * The following functions will only work for the R4000!
  66.  */
  67.  
  68. extern __inline__ void set_bit(int nr, void *addr)
  69. {
  70.     int    mask, mw;
  71.  
  72.     addr += ((nr >> 3) & ~3);
  73.     mask = 1 << (nr & 0x1f);
  74.     do {
  75.         mw = load_linked(addr);
  76.     } while (!store_conditional(addr, mw|mask));
  77. }
  78.  
  79. extern __inline__ void clear_bit(int nr, void *addr)
  80. {
  81.     int    mask, mw;
  82.  
  83.     addr += ((nr >> 3) & ~3);
  84.     mask = 1 << (nr & 0x1f);
  85.     do {
  86.         mw = load_linked(addr);
  87.         }
  88.     while (!store_conditional(addr, mw & ~mask));
  89. }
  90.  
  91. extern __inline__ void change_bit(int nr, void *addr)
  92. {
  93.     int    mask, mw;
  94.  
  95.     addr += ((nr >> 3) & ~3);
  96.     mask = 1 << (nr & 0x1f);
  97.     do {
  98.         mw = load_linked(addr);
  99.     } while (!store_conditional(addr, mw ^ mask));
  100. }
  101.  
  102. extern __inline__ int test_and_set_bit(int nr, void *addr)
  103. {
  104.     int    mask, retval, mw;
  105.  
  106.     addr += ((nr >> 3) & ~3);
  107.     mask = 1 << (nr & 0x1f);
  108.     do {
  109.         mw = load_linked(addr);
  110.         retval = (mask & mw) != 0;
  111.     } while (!store_conditional(addr, mw|mask));
  112.  
  113.     return retval;
  114. }
  115.  
  116. extern __inline__ int test_and_clear_bit(int nr, void *addr)
  117. {
  118.     int    mask, retval, mw;
  119.  
  120.     addr += ((nr >> 3) & ~3);
  121.     mask = 1 << (nr & 0x1f);
  122.     do {
  123.         mw = load_linked(addr);
  124.         retval = (mask & mw) != 0;
  125.         }
  126.     while (!store_conditional(addr, mw & ~mask));
  127.  
  128.     return retval;
  129. }
  130.  
  131. extern __inline__ int test_and_change_bit(int nr, void *addr)
  132. {
  133.     int    mask, retval, mw;
  134.  
  135.     addr += ((nr >> 3) & ~3);
  136.     mask = 1 << (nr & 0x1f);
  137.     do {
  138.         mw = load_linked(addr);
  139.         retval = (mask & mw) != 0;
  140.     } while (!store_conditional(addr, mw ^ mask));
  141.  
  142.     return retval;
  143. }
  144.  
  145. #else /* MIPS I */
  146.  
  147. extern __inline__ void set_bit(int nr, void * addr)
  148. {
  149.     int    mask;
  150.     int    *a = addr;
  151.     __bi_flags;
  152.  
  153.     a += nr >> 5;
  154.     mask = 1 << (nr & 0x1f);
  155.     __bi_save_flags(flags);
  156.     __bi_cli();
  157.     *a |= mask;
  158.     __bi_restore_flags(flags);
  159. }
  160.  
  161. extern __inline__ void clear_bit(int nr, void * addr)
  162. {
  163.     int    mask;
  164.     int    *a = addr;
  165.     __bi_flags;
  166.  
  167.     a += nr >> 5;
  168.     mask = 1 << (nr & 0x1f);
  169.     __bi_save_flags(flags);
  170.     __bi_cli();
  171.     *a &= ~mask;
  172.     __bi_restore_flags(flags);
  173. }
  174.  
  175. extern __inline__ void change_bit(int nr, void * addr)
  176. {
  177.     int    mask;
  178.     int    *a = addr;
  179.     __bi_flags;
  180.  
  181.     a += nr >> 5;
  182.     mask = 1 << (nr & 0x1f);
  183.     __bi_save_flags(flags);
  184.     __bi_cli();
  185.     *a ^= mask;
  186.     __bi_restore_flags(flags);
  187. }
  188.  
  189. extern __inline__ int test_and_set_bit(int nr, void * addr)
  190. {
  191.     int    mask, retval;
  192.     int    *a = addr;
  193.     __bi_flags;
  194.  
  195.     a += nr >> 5;
  196.     mask = 1 << (nr & 0x1f);
  197.     __bi_save_flags(flags);
  198.     __bi_cli();
  199.     retval = (mask & *a) != 0;
  200.     *a |= mask;
  201.     __bi_restore_flags(flags);
  202.  
  203.     return retval;
  204. }
  205.  
  206. extern __inline__ int test_and_clear_bit(int nr, void * addr)
  207. {
  208.     int    mask, retval;
  209.     int    *a = addr;
  210.     __bi_flags;
  211.  
  212.     a += nr >> 5;
  213.     mask = 1 << (nr & 0x1f);
  214.     __bi_save_flags(flags);
  215.     __bi_cli();
  216.     retval = (mask & *a) != 0;
  217.     *a &= ~mask;
  218.     __bi_restore_flags(flags);
  219.  
  220.     return retval;
  221. }
  222.  
  223. extern __inline__ int test_and_change_bit(int nr, void * addr)
  224. {
  225.     int    mask, retval;
  226.     int    *a = addr;
  227.     __bi_flags;
  228.  
  229.     a += nr >> 5;
  230.     mask = 1 << (nr & 0x1f);
  231.     __bi_save_flags(flags);
  232.     __bi_cli();
  233.     retval = (mask & *a) != 0;
  234.     *a ^= mask;
  235.     __bi_restore_flags(flags);
  236.  
  237.     return retval;
  238. }
  239.  
  240. #undef __bi_flags
  241. #undef __bi_cli()
  242. #undef __bi_save_flags(x)
  243. #undef __bi_restore_flags(x)
  244.  
  245. #endif /* MIPS I */
  246.  
  247. extern __inline__ int test_bit(int nr, const void *addr)
  248. {
  249.     return ((1UL << (nr & 31)) & (((const unsigned int *) addr)[nr >> 5])) != 0;
  250. }
  251.  
  252. #ifndef __MIPSEB__
  253.  
  254. /* Little endian versions. */
  255.  
  256. extern __inline__ int find_first_zero_bit (void *addr, unsigned size)
  257. {
  258.     unsigned long dummy;
  259.     int res;
  260.  
  261.     if (!size)
  262.         return 0;
  263.  
  264.     __asm__ (".set\tnoreorder\n\t"
  265.         ".set\tnoat\n"
  266.         "1:\tsubu\t$1,%6,%0\n\t"
  267.         "blez\t$1,2f\n\t"
  268.         "lw\t$1,(%5)\n\t"
  269.         "addiu\t%5,4\n\t"
  270. #if (_MIPS_ISA == _MIPS_ISA_MIPS2) || (_MIPS_ISA == _MIPS_ISA_MIPS3) || \
  271.     (_MIPS_ISA == _MIPS_ISA_MIPS4) || (_MIPS_ISA == _MIPS_ISA_MIPS5)
  272.         "beql\t%1,$1,1b\n\t"
  273.         "addiu\t%0,32\n\t"
  274. #else
  275.         "addiu\t%0,32\n\t"
  276.         "beq\t%1,$1,1b\n\t"
  277.         "nop\n\t"
  278.         "subu\t%0,32\n\t"
  279. #endif
  280. #ifdef __MIPSEB__
  281. #error "Fix this for big endian"
  282. #endif /* __MIPSEB__ */
  283.         "li\t%1,1\n"
  284.         "1:\tand\t%2,$1,%1\n\t"
  285.         "beqz\t%2,2f\n\t"
  286.         "sll\t%1,%1,1\n\t"
  287.         "bnez\t%1,1b\n\t"
  288.         "add\t%0,%0,1\n\t"
  289.         ".set\tat\n\t"
  290.         ".set\treorder\n"
  291.         "2:"
  292.         : "=r" (res),
  293.           "=r" (dummy),
  294.           "=r" (addr)
  295.         : "0" ((signed int) 0),
  296.           "1" ((unsigned int) 0xffffffff),
  297.           "2" (addr),
  298.           "r" (size)
  299.         : "$1");
  300.  
  301.     return res;
  302. }
  303.  
  304. extern __inline__ int find_next_zero_bit (void * addr, int size, int offset)
  305. {
  306.     unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
  307.     int set = 0, bit = offset & 31, res;
  308.     unsigned long dummy;
  309.     
  310.     if (bit) {
  311.         /*
  312.          * Look for zero in first byte
  313.          */
  314. #ifdef __MIPSEB__
  315. #error "Fix this for big endian byte order"
  316. #endif
  317.         __asm__(".set\tnoreorder\n\t"
  318.             ".set\tnoat\n"
  319.             "1:\tand\t$1,%4,%1\n\t"
  320.             "beqz\t$1,1f\n\t"
  321.             "sll\t%1,%1,1\n\t"
  322.             "bnez\t%1,1b\n\t"
  323.             "addiu\t%0,1\n\t"
  324.             ".set\tat\n\t"
  325.             ".set\treorder\n"
  326.             "1:"
  327.             : "=r" (set),
  328.               "=r" (dummy)
  329.             : "0" (0),
  330.               "1" (1 << bit),
  331.               "r" (*p)
  332.             : "$1");
  333.         if (set < (32 - bit))
  334.             return set + offset;
  335.         set = 32 - bit;
  336.         p++;
  337.     }
  338.     /*
  339.      * No zero yet, search remaining full bytes for a zero
  340.      */
  341.     res = find_first_zero_bit(p, size - 32 * (p - (unsigned int *) addr));
  342.     return offset + set + res;
  343. }
  344.  
  345. #endif /* !(__MIPSEB__) */
  346.  
  347. /*
  348.  * ffz = Find First Zero in word. Undefined if no zero exists,
  349.  * so code should check against ~0UL first..
  350.  */
  351. extern __inline__ unsigned long ffz(unsigned long word)
  352. {
  353.     unsigned int    __res;
  354.     unsigned int    mask = 1;
  355.  
  356.     __asm__ (
  357.         ".set\tnoreorder\n\t"
  358.         ".set\tnoat\n\t"
  359.         "move\t%0,$0\n"
  360.         "1:\tand\t$1,%2,%1\n\t"
  361.         "beqz\t$1,2f\n\t"
  362.         "sll\t%1,1\n\t"
  363.         "bnez\t%1,1b\n\t"
  364.         "addiu\t%0,1\n\t"
  365.         ".set\tat\n\t"
  366.         ".set\treorder\n"
  367.         "2:\n\t"
  368.         : "=&r" (__res), "=r" (mask)
  369.         : "r" (word), "1" (mask)
  370.         : "$1");
  371.  
  372.     return __res;
  373. }
  374.  
  375. #ifdef __KERNEL__
  376.  
  377. /*
  378.  * ffs: find first bit set. This is defined the same way as
  379.  * the libc and compiler builtin ffs routines, therefore
  380.  * differs in spirit from the above ffz (man ffs).
  381.  */
  382.  
  383. #define ffs(x) generic_ffs(x)
  384.  
  385. /*
  386.  * hweightN: returns the hamming weight (i.e. the number
  387.  * of bits set) of a N-bit word
  388.  */
  389.  
  390. #define hweight32(x) generic_hweight32(x)
  391. #define hweight16(x) generic_hweight16(x)
  392. #define hweight8(x) generic_hweight8(x)
  393.  
  394. #endif /* __KERNEL__ */
  395.  
  396. #ifdef __MIPSEB__
  397. /* For now I steal the Sparc C versions, no need for speed, just need to
  398.  * get it working.
  399.  */
  400. /* find_next_zero_bit() finds the first zero bit in a bit string of length
  401.  * 'size' bits, starting the search at bit 'offset'. This is largely based
  402.  * on Linus's ALPHA routines, which are pretty portable BTW.
  403.  */
  404.  
  405. extern __inline__ int find_next_zero_bit(void *addr, int size, int offset)
  406. {
  407.     unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
  408.     unsigned long result = offset & ~31UL;
  409.     unsigned long tmp;
  410.  
  411.     if (offset >= size)
  412.         return size;
  413.     size -= result;
  414.     offset &= 31UL;
  415.     if (offset) {
  416.         tmp = *(p++);
  417.         tmp |= ~0UL >> (32-offset);
  418.         if (size < 32)
  419.             goto found_first;
  420.         if (~tmp)
  421.             goto found_middle;
  422.         size -= 32;
  423.         result += 32;
  424.     }
  425.     while (size & ~31UL) {
  426.         if (~(tmp = *(p++)))
  427.             goto found_middle;
  428.         result += 32;
  429.         size -= 32;
  430.     }
  431.     if (!size)
  432.         return result;
  433.     tmp = *p;
  434.  
  435. found_first:
  436.     tmp |= ~0UL << size;
  437. found_middle:
  438.     return result + ffz(tmp);
  439. }
  440.  
  441. /* Linus sez that gcc can optimize the following correctly, we'll see if this
  442.  * holds on the Sparc as it does for the ALPHA.
  443.  */
  444.  
  445. #define find_first_zero_bit(addr, size) \
  446.         find_next_zero_bit((addr), (size), 0)
  447.  
  448. #endif /* (__MIPSEB__) */
  449.  
  450. /* Now for the ext2 filesystem bit operations and helper routines. */
  451.  
  452. #ifdef __MIPSEB__
  453. extern __inline__ int ext2_set_bit(int nr,void * addr)
  454. {
  455.     int        mask, retval, flags;
  456.     unsigned char    *ADDR = (unsigned char *) addr;
  457.  
  458.     ADDR += nr >> 3;
  459.     mask = 1 << (nr & 0x07);
  460.     save_flags(flags); cli();
  461.     retval = (mask & *ADDR) != 0;
  462.     *ADDR |= mask;
  463.     restore_flags(flags);
  464.     return retval;
  465. }
  466.  
  467. extern __inline__ int ext2_clear_bit(int nr, void * addr)
  468. {
  469.     int        mask, retval, flags;
  470.     unsigned char    *ADDR = (unsigned char *) addr;
  471.  
  472.     ADDR += nr >> 3;
  473.     mask = 1 << (nr & 0x07);
  474.     save_flags(flags); cli();
  475.     retval = (mask & *ADDR) != 0;
  476.     *ADDR &= ~mask;
  477.     restore_flags(flags);
  478.     return retval;
  479. }
  480.  
  481. extern __inline__ int ext2_test_bit(int nr, const void * addr)
  482. {
  483.     int            mask;
  484.     const unsigned char    *ADDR = (const unsigned char *) addr;
  485.  
  486.     ADDR += nr >> 3;
  487.     mask = 1 << (nr & 0x07);
  488.     return ((mask & *ADDR) != 0);
  489. }
  490.  
  491. #define ext2_find_first_zero_bit(addr, size) \
  492.         ext2_find_next_zero_bit((addr), (size), 0)
  493.  
  494. extern __inline__ unsigned long ext2_find_next_zero_bit(void *addr, unsigned long size, unsigned long offset)
  495. {
  496.     unsigned long *p = ((unsigned long *) addr) + (offset >> 5);
  497.     unsigned long result = offset & ~31UL;
  498.     unsigned long tmp;
  499.  
  500.     if (offset >= size)
  501.         return size;
  502.     size -= result;
  503.     offset &= 31UL;
  504.     if(offset) {
  505.         /* We hold the little endian value in tmp, but then the
  506.          * shift is illegal. So we could keep a big endian value
  507.          * in tmp, like this:
  508.          *
  509.          * tmp = __swab32(*(p++));
  510.          * tmp |= ~0UL >> (32-offset);
  511.          *
  512.          * but this would decrease preformance, so we change the
  513.          * shift:
  514.          */
  515.         tmp = *(p++);
  516.         tmp |= __swab32(~0UL >> (32-offset));
  517.         if(size < 32)
  518.             goto found_first;
  519.         if(~tmp)
  520.             goto found_middle;
  521.         size -= 32;
  522.         result += 32;
  523.     }
  524.     while(size & ~31UL) {
  525.         if(~(tmp = *(p++)))
  526.             goto found_middle;
  527.         result += 32;
  528.         size -= 32;
  529.     }
  530.     if(!size)
  531.         return result;
  532.     tmp = *p;
  533.  
  534. found_first:
  535.     /* tmp is little endian, so we would have to swab the shift,
  536.      * see above. But then we have to swab tmp below for ffz, so
  537.      * we might as well do this here.
  538.      */
  539.     return result + ffz(__swab32(tmp) | (~0UL << size));
  540. found_middle:
  541.     return result + ffz(__swab32(tmp));
  542. }
  543. #else /* !(__MIPSEB__) */
  544.  
  545. /* Native ext2 byte ordering, just collapse using defines. */
  546. #define ext2_set_bit(nr, addr) test_and_set_bit((nr), (addr))
  547. #define ext2_clear_bit(nr, addr) test_and_clear_bit((nr), (addr))
  548. #define ext2_test_bit(nr, addr) test_bit((nr), (addr))
  549. #define ext2_find_first_zero_bit(addr, size) find_first_zero_bit((addr), (size))
  550. #define ext2_find_next_zero_bit(addr, size, offset) \
  551.                 find_next_zero_bit((addr), (size), (offset))
  552.  
  553. #endif /* !(__MIPSEB__) */
  554.  
  555. /*
  556.  * Bitmap functions for the minix filesystem.
  557.  * FIXME: These assume that Minix uses the native byte/bitorder.
  558.  * This limits the Minix filesystem's value for data exchange very much.
  559.  */
  560. #define minix_set_bit(nr,addr) test_and_set_bit(nr,addr)
  561. #define minix_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
  562. #define minix_test_bit(nr,addr) test_bit(nr,addr)
  563. #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
  564.  
  565. #endif /* __ASM_MIPS_BITOPS_H */
  566.